「Violet」天使玩偶/SJY摆棋子

发表于 | 分类于 | | 浏览量： 次

卡常CDQ？难受！

传送门

洛谷P4169

BZOJ2716

题解

首先，如果没有计算距离的式子里没有绝对值的话，那么就可以把每个玩偶的权值定为X+Y，然后对于每一次询问，找一个满足要求且权值最大的即可。这个可以通过CDQ分治实现。

由于有绝对值，所以需要拆分成四种情况来考虑。

然后常数就上天了。

适当卡常就能过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000005,inf=0x3F3F3F3F;
int n,m,q,ans[500005],len,Tree[maxn],MX,MY;
struct FastIO
{
	static const int S=16777216;
	char buf[S],*L,*R;int stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	FastIO& operator >> (int& ret)
	{
		ret=0;int f=1;char ch=nc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
		return *this;
	}
	FastIO& operator << (int x)
	{
		if(x<0){pc('-');x=-x;}
		do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);
		return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
}fin,fout;
inline void Update(int pos,int val){while(pos<=1000000){if(val>Tree[pos]) Tree[pos]=val;pos+=pos&-pos;}}
inline int Query(int pos){int ret=-inf;while(pos>0){if(Tree[pos]>ret) ret=Tree[pos];pos-=pos&-pos;}return ret;}
inline void Build(){for(int i=0;i<=1000000;i++) Tree[i]=-inf;}
inline void Del(int pos){while(pos<=1000000){Tree[pos]=-inf;pos+=pos&-pos;}}
struct Command{int t,X,Y,typ,W,id;}A[maxn],B[maxn],C[maxn];
inline bool cmp1(const Command& a,const Command& b){return a.t<b.t;}
inline bool cmp2(const Command& a,const Command& b){return a.X<b.X||(a.X==b.X&&a.t<b.t);}
void CDQ(int L,int R)
{
	if(L==R) return;
	register int M=(L+R)>>1,mid=A[M].t;
	CDQ(L,M);CDQ(M+1,R);
	merge(A+L,A+M+1,A+M+1,A+R+1,B+1,cmp2);
	memcpy(A+L,B+1,(R-L+1)*sizeof(Command));
	for(register int i=L;i<=R;i++)
	{
		if(A[i].t<=mid&&A[i].typ==1) Update(A[i].Y,A[i].X+A[i].Y);
		else if(A[i].t>mid&&A[i].typ==2) A[i].W=min(A[i].W,A[i].X+A[i].Y-Query(A[i].Y));
	}
	for(register int i=L;i<=R;i++) if(A[i].t<=mid&&A[i].typ==1) Del(A[i].Y);
}
inline void Init()
{
	int XM=0,YM=0;len=0;
	for(register int i=1;i<=n+m;i++) if(C[i].typ==2){if(C[i].X>XM) XM=C[i].X;if(C[i].Y>YM) YM=C[i].Y;}
	for(register int i=1;i<=n+m;i++) if(C[i].X<=XM&&C[i].Y<=YM) A[++len]=C[i];
	sort(A+1,A+1+len,cmp1);
}
inline void Update(){for(int i=1;i<=len;i++) if(A[i].W<ans[A[i].id]) ans[A[i].id]=A[i].W;}
inline void Solve()
{
	memset(ans,63,sizeof(ans));
	memcpy(C,A,sizeof(Command)*(n+m+3));
	Init();CDQ(1,len);Update();
	for(register int i=1;i<=n+m;i++) C[i].X=MX-C[i].X;
	Init();CDQ(1,len);Update();
	for(register int i=1;i<=n+m;i++) C[i].Y=MY-C[i].Y;
	Init();CDQ(1,len);Update();
	for(register int i=1;i<=n+m;i++) C[i].X=MX-C[i].X;
	Init();CDQ(1,len);Update();
}
int main()
{
	fin>>n>>m;
	for(register int i=1;i<=n;i++)
	{
		fin>>A[i].X>>A[i].Y;
		A[i].X++;A[i].Y++;
		A[i].typ=1;A[i].t=i;
		if(A[i].X>MX) MX=A[i].X;
		if(A[i].Y>MY) MY=A[i].Y;
	}
	for(register int i=n+1;i<=m+n;i++)
	{
		fin>>A[i].typ>>A[i].X>>A[i].Y;A[i].t=i;
		A[i].X++;A[i].Y++;
		if(A[i].X>MX) MX=A[i].X;
		if(A[i].Y>MY) MY=A[i].Y;
		if(A[i].typ==2){A[i].id=++q;A[i].W=inf;}
	}
	MX++;MY++;
	Build();
	Solve();
	for(int i=1;i<=q;i++)
		fout<<ans[i]<<'\n';
	return 0;
}